/**
 * @file filename.cpp
 * @brief nullptr关键字用于标识空指针，与NULL不同，NULL为0
 * @author Monomania (1301519350@qq.com)
 * @version 0.1
 * @date 2021-09-23
 */
#include<iostream>
#include <vector> 
#include <string>
#include <list>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue> 
#include <stack>
#include <algorithm> // std::minmax_element
#include <boost/algorithm/string.hpp>
#include <functional>
#include <iterator>
#include<numeric>  // 用于对vector求和----accumulate函数
// #define NDEBUG
#include <assert.h>
using namespace boost;   // 支持string的操作
using namespace std;

#define OK 1
#define ERROR 0
#define TRUE true
#define FALSE false
// 定义一个不可能的数
#define INF   -99999  
#define MAXSIZE 20 /* 存储空间初始分配量 */

typedef int Status; 
typedef int SElemType; /* SElemType类型根据实际情况而定，这里假设为int */

// 遍历
template<typename T> //整数或浮点数皆可使用,若要使用类(class)或结构体(struct)时必须重载大于(>)运算符
void visit_arr(vector<T>& arr, string const str){
    cout << str << ": ";
    // typename T::const_iterator it = arr.begin();
    for(auto it=arr.begin();it!=arr.end();++it){
        cout << *it <<" ";
    }
    cout<<endl;
}

// 遍历
// template<typename T> //整数或浮点数皆可使用,若要使用类(class)或结构体(struct)时必须重载大于(>)运算符
void visit2_arr(vector<int>& arr, string const str){
    cout << str << ": ";
    for(int i; i < arr.size(); ++i){
        cout << arr[i] << " ";
    }
    cout<<endl;
}



// 链表结点
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

void visit_list(ListNode* head){
    ListNode* tmp = head;
    while(tmp != nullptr){
        cout << tmp->val << ' ';
        tmp = tmp->next;
    }
    cout << endl;
}

// 二叉树--孩子兄弟表示法
//Definition for a binary tree node.// 二叉树--孩子兄弟表示法
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

// https://leetcode-cn.com/problems/3sum/
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;
        if (nums.size() < 3) return result;
        sort(nums.begin(), nums.end());
        visit_arr(nums,"排序后输入");
        // 找出a + b + c = 0
        // a 和 c 固定，找b----target为9
        // for(int i = 0; i < nums.size()-2; i++)
        // 大幅提高效率---因为排序过了，所以最小的如果大于0了就不用再找了
        for(int i = 0; i < nums.size()-2 && nums[i] <= 0; i++){
            int left = i+1;
            int right = nums.size()-1;
            // 去重:
            if (i > 0 && nums[i] == nums[i - 1]) continue;

            cout << "========" << i << " - " << nums[i] << "========" <<endl;
            while(left < right){
                if (nums[left]+nums[right]+nums[i] == 0){
                    result.push_back({nums[left], nums[right],nums[i]});
                    // 找到元素后，双指针同时收缩
                    right--;
                    left++;
                    // 去重----要放上面
                    while (right > left && nums[left] == nums[left - 1]) left++;
                    while (right > left && nums[right] == nums[right + 1]) right--;

                } else if (nums[left]+nums[right]+nums[i] > 0) {
                    right--;
                } else {
                    left++;
                }
            }
            for (auto i = 0; i < result.size();i++){
                visit_arr(result[i],"结果");
            }
        }
        return result;
    }
};


int main(int argc, const char** argv) {
    Solution solu = Solution();
    // vector<int> nums = {-1,0,1,2,-1,-4}; // 有重复
    // vector<int> nums = {-2,0,0,2,2}; // 有重复
    // vector<int> nums = {0,0,0,0}; // 有重复
    // vector<int> nums = {0,0,0}; // 有重复
    vector<int> nums = {-2,0,1,1,2}; // 有重复

    
    time_t start = time(NULL);
    cout << "start time is " << start << endl;

    vector<vector<int>> result = solu.threeSum(nums);
    for (auto i = 0; i < result.size();i++){
        visit_arr(result[i],"结果");
    }
    
    time_t end = time(NULL);
    cout << "end time is " << start << endl;
    cout << "耗时：" << end*100-start*100 << " s." <<endl;


    return 0;
}